package zuochengyun;

public class KthMinOfTwoSortedArray {

	
	//在两个有序数组中找到第k小的数字
	public int findKthNum(int[] arr1, int[] arr2, int k){
		if(arr1 == null || arr2 == null){
			throw new IllegalArgumentException("the input array is invalid");
		}
		if(k < 1 || k > arr1.length + arr2.length){
			throw new IllegalArgumentException("the input k is invalid");
		}
		int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
		int[] shorts = arr1.length < arr2.length ? arr1 : arr2;
		int longLength = longs.length;
		int shortLength = shorts.length;
		if(k <= shortLength){
			//如果k小于等于shortLength,那就直接返回0 -- k中的中位数
			return getUpMedian(shorts, longs, 0, k - 1, 0, k - 1);
		}else if(k < longLength){
			//显然长数组中有一段不可能是第k小的，比如10个与27个，要求第17小的
			//第27个的中[1 ...6]肯定不可能，[18... 27]也不可能
			//所以只能是[7 ... 17]但是这有11个数，于是要想法排除7
			if(longs[k - shortLength - 1] > shorts[shortLength - 1]){
				return longs[k - shortLength];
			}else{
				return getUpMedian(shorts, longs, 0, shortLength - 1, k - shortLength, k - 1);
			}
		}else{
			return getUpMedian(shorts, longs, k - longLength, shortLength - 1, k - shortLength, longLength - 1);
		}
	}
	
	
	
	public int getUpMedian(int[] arr1, int[] arr2, int start1, int end1, int start2, int end2){
		if(arr1 == null || arr2 == null || arr1.length != arr2.length){
			throw new IllegalArgumentException("the input is invalid");
		}
		int mid1 = 0;
		int mid2 = 0;
		int offset = 0;		//用来判断数组是奇数还是偶数个
		//注意，两个数组的长度始终要保持一样
		while(start1 < end1){
			mid1 = (start1 + end1) / 2;
			mid2 = (start2 + end2) / 2;
			offset = ((end1 - start1 + 1) & 1) ^ 1;		//为奇数时为0，偶数是为1
			if(arr1[mid1] == arr2[mid2]){
				//显然如果相等就可以直接返回
				return arr1[mid1];
			}else if(arr1[mid1] > arr2[mid2]){
				//如果不相等，那么就需要二分。比如[1 2 3 4 5](数字代表是第几个数，并不是值)
				//[1'  2'  3'  4'  5'](同上，表示第二个数组的第几个数)
				//如果 3 > 3', 那么说明4  5 肯定不可能是，1'  2' 肯定不可能是，所以只有[1 2 3]和[3'  4'  5']
				//于是end1 = mid1， start2 = mid2 
				//对于偶数的不一样，所以我们需要一个offse
				end1 = mid1;
				start2 = mid2 + offset;
			}else{
				//对于小于的情况，同理分析
				end2 = mid2;
				start1 = mid1 + offset;
			}
		}
		return Math.min(arr1[start1], arr2[start2]);
	}
}
